GATE PYQ

GATE IT 2006

Q21.
Which of the following statement(s) is TRUE? I. A hash function takes a message of arbitrary length and generates a fixed length code. II. A hash function takes a message of fixed length and generates a code of variable length. III. A hash function may give the same hash value for distinct messages.

Q22.
Consider a relation R with five attributes V, W, X, Y, and Z. The following functional dependencies hold: VY \rightarrow W, WX \rightarrow Z, \text{and }ZY \rightarrow V. Which of the following is a candidate key for R?

Q23.
The memory locations 1000,1001 and 1020 have data values 18,1 and 16 respectively before the following program is executed. \begin{array}{llll} \text{MOVI} & \text{$R_s, 1$} && \text{; Move immediate} \\ \text{LOAD} & \text{$R_d, 1000(R_s)$} && \text{; Load from memory}\\ \text{ADDI} & \text{$ R_d, 1000$} && \text{; Add immediate}\\ \text{STOREI} & \text{$0(R_d), 20$} && \text{; Store immediate} \end{array} Which of the statements below is TRUE after the program is executed ?

Q24.
A pipelined processor uses a 4-stage instruction pipeline with the following stages: Instruction fetch (IF), Instruction decode (ID), Execute (EX) and Writeback (WB). The arithmetic operations as well as the load and store operations are carried out in the EX stage. The sequence of instructions corresponding to the statement X = (S - R * (P + Q))/T is given below. The values of variables P, Q, R, S and T are available in the registers R0, R1, R2, R3 and R4 respectively, before the execution of the instruction sequence. \begin{array}{lll} \text{ADD} & \text{$R5,R0,R1$} & \text{$;R5$} \leftarrow \text{R0 + R1} \\ \text{MUL}& \text{$R6,R2,R5$} & \text{$;R6$} \leftarrow \text{R2 * R5} \\ \text{SUB} & \text{$R5,R3,R6$} & \text{$;R5$} \leftarrow \text{R3 -R6} \\ \text{DIV} &\text{$R6,R5,R4$} & \text{$;R6$} \leftarrow \text{R5/R4} \\ \text{STORE} &\text{$R6,X$}& \text{$;X$} \leftarrow \text{R6} \\ \end{array} The number of Read-After-Write (RAW) dependencies, Write-After-Read( WAR) dependencies, and Write-After-Write (WAW) dependencies in the sequence of instructions are, respectively,

Q25.
A pipelined processor uses a 4-stage instruction pipeline with the following stages: Instruction fetch (IF), Instruction decode (ID), Execute (EX) and Writeback (WB). The arithmetic operations as well as the load and store operations are carried out in the EX stage. The sequence of instructions corresponding to the statement X = (S - R * (P + Q))/T is given below. The values of variables P, Q, R, S and T are available in the registers R0, R1, R2, R3 and R4 respectively, before the execution of the instruction sequence. \begin{array}{lll} \text{ADD} & \text{$R5,R0,R1$} & \text{$;R5$} \leftarrow \text{R0 + R1} \\ \text{MUL}& \text{$R6,R2,R5$} & \text{$;R6$} \leftarrow \text{R2 * R5} \\ \text{SUB} & \text{$R5,R3,R6$} & \text{$;R5$} \leftarrow \text{R3 -R6} \\ \text{DIV} &\text{$R6,R5,R4$} & \text{$;R6$} \leftarrow \text{R5/R4} \\ \text{STORE} &\text{$R6,X$}& \text{$;X$} \leftarrow \text{R6} \\ \end{array} The IF, ID and WB stages take 1 clock cycle each. The EX stage takes 1 clock cycle each for the ADD, SUB and STORE operations, and 3 clock cycles each for MUL and DIV operations. Operand forwarding from the EX stage to the ID stage is used. The number of clock cycles required to complete the sequence of instructions is

Q26.
x+y/2=9 3x+y=10 What can be said about the Gauss-Siedel iterative method for solving the above set of linear equations?

Q27.
Match the following iterative methods for solving algebraic equations and their orders of convergence.\begin{array}{|l|l|l|l|} \hline & \text { Method } & & \text { Order of Convergence } \\ \hline \text { 1. } & \text { Bisection } & \text { P. } & \text { 2 or more } \\ \hline \text { 2. } & \text { Newton-Raphson } & \text { Q. } & 1.62 \\ \hline \text { 3. } & \text { Secant } & \text { R. } & 1 \\ \hline \text { 4. } & \text { Regula falsi } & \text { S. } & 1 \text { bit per iteration } \\ \hline \end{array}

Q28.
x+y/2=9 3x+y=10 The value of the Frobenius norm for the above system of equations is

Q29.
The process state transition diagram of an operating system is as given below. Which of the following must be FALSE about the above operating system?

Q30.
The wait and signal operations of a monitor are implemented using semaphores as follows. In the following, x is a condition variable, mutex is a semaphore initialized to 1, x_sem is a semaphore initialized to 0, x_count is the number of processes waiting on semaphore x_sem, initially 0, next is a semaphore initialized to 0, next_count is the number of processes waiting on semaphore next, initially 0. The body of each procedure that is visible outside the monitor is replaced with the following: P(mutex); ... body of procedure ... if (next_count > 0) V(next); else V(mutex); Each occurrence of x.wait is replaced with the following: x_count = x_count + 1; if (next_count > 0) V(next); else V(mutex); ------------------------------------------------------------ E1; x_count = x_count - 1; Each occurrence of x.signal is replaced with the following: if (x_count > 0) { next_count = next_count + 1; ------------------- E2; P(next); next_count = next_count - 1; } For correct implementation of the monitor, statements E1 and E2 are, respectively,